package com.sheng.leetcode.year2022.swordfingeroffer.day23;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/09/21
 *<p>
 * 剑指 Offer 39. 数组中出现次数超过一半的数字<p>
 *<p>
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。<p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。<p>
 *<p>
 * 示例1:<p>
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]<p>
 * 输出: 2<p>
 *<p>
 * 限制：<p>
 *<p>
 * 1 <= 数组长度 <= 50000<p>
 *<p>
 * 注意：本题与主站 169 题相同：<a href="https://leetcode-cn.com/problems/majority-element/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0039 {

    @Test
    public void test01() {
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(new Solution().majorityElement(nums));
    }
}
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(16);
        int length = nums.length;
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) >= length / 2 + 1) {
                return num;
            }
        }
        return -1;
    }
}

// 优质解答
//class Solution {
//    public int majorityElement(int[] nums) {
//        Arrays.sort(nums);
//        return nums[nums.length / 2];
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-pvh8/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//class Solution {
//    private Map<Integer, Integer> countNums(int[] nums) {
//        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
//        for (int num : nums) {
//            if (!counts.containsKey(num)) {
//                counts.put(num, 1);
//            } else {
//                counts.put(num, counts.get(num) + 1);
//            }
//        }
//        return counts;
//    }
//
//    public int majorityElement(int[] nums) {
//        Map<Integer, Integer> counts = countNums(nums);
//
//        Map.Entry<Integer, Integer> majorityEntry = null;
//        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
//            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
//                majorityEntry = entry;
//            }
//        }
//
//        return majorityEntry.getKey();
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-pvh8/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
